home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / graph_alg / _planar.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  17.0 KB  |  700 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _planar.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17. #include <LEDA/stack.h>
  18. #include <LEDA/graph.h>
  19. #include <LEDA/graph_alg.h>
  20.  
  21. static void dfs_in_make_biconnected_graph(graph & G, node v, int &dfs_count,
  22.   node_array < bool > &reached,
  23.   node_array < int >&dfsnum, node_array < int >&lowpt,
  24.   node_array < node > &parent);
  25.  
  26. const int left = 1;
  27. const int right = 2;
  28.  
  29. static void dfs_in_reorder(list < edge > &Del, node v, int &dfs_count,
  30.   node_array < bool > &reached,
  31.   node_array < int >&dfsnum,
  32.   node_array < int >&lowpt1, node_array < int >&lowpt2,
  33.   node_array < node > &parent);
  34.  
  35. class block
  36. {
  37.   private:
  38.   list < int >Latt, Ratt;    /* list of attachments */
  39.    list < edge > Lseg, Rseg;    /* list of segments represented by their *
  40.                  * defining edges */
  41.  
  42.    public:
  43.  
  44.    block(edge e, list < int >&A) {
  45.     Lseg.append(e);
  46.     Latt.conc(A);
  47. /* the other two lists are empty */
  48.   } ~block() {
  49.   }
  50.  
  51.   void flip() {
  52.     list < int >ha;
  53.      list < edge > he;
  54. /* we first interchange |Latt| and |Ratt| and then |Lseg| and |Rseg| */
  55.      ha.conc(Ratt);
  56.      Ratt.conc(Latt);
  57.      Latt.conc(ha);
  58.      he.conc(Rseg);
  59.      Rseg.conc(Lseg);
  60.      Lseg.conc(he);
  61.   } int head_of_Latt() {
  62.     return Latt.head();
  63.   }
  64.   bool empty_Latt() {
  65.     return Latt.empty();
  66.   }
  67.   int head_of_Ratt() {
  68.     return Ratt.head();
  69.   }
  70.   bool empty_Ratt() {
  71.     return Ratt.empty();
  72.   }
  73.   bool left_interlace(stack < block * >&S) {
  74. /* check for interlacing with the left side of the topmost block of
  75.  * |S| */
  76.     if (Latt.empty())
  77.       error_handler(1, "Latt is never empty");
  78.  
  79.     if (!S.empty() && !((S.top())->empty_Latt()) &&
  80.       Latt.tail() < (S.top())->head_of_Latt())
  81.       return true;
  82.     else
  83.       return false;
  84.   }
  85.   bool right_interlace(stack < block * >&S) {
  86. /* check for interlacing with the right side of the topmost block of
  87.  * |S| */
  88.     if (Latt.empty())
  89.       error_handler(1, "Latt is never empty");
  90.  
  91.     if (!S.empty() && !((S.top())->empty_Ratt()) &&
  92.       Latt.tail() < (S.top())->head_of_Ratt())
  93.       return true;
  94.     else
  95.       return false;
  96.   }
  97.   void combine(block * Bprime) {
  98. /* add block Bprime to the rear of |this| block */
  99.     Latt.conc(Bprime->Latt);
  100.     Ratt.conc(Bprime->Ratt);
  101.     Lseg.conc(Bprime->Lseg);
  102.     Rseg.conc(Bprime->Rseg);
  103.     delete(Bprime);
  104.   } bool clean(int dfsnum_w, edge_array < int >&alpha) {
  105. /* remove all attachments to |w|; there may be several */
  106.     while (!Latt.empty() && Latt.head() == dfsnum_w)
  107.       Latt.pop();
  108.     while (!Ratt.empty() && Ratt.head() == dfsnum_w)
  109.       Ratt.pop();
  110.  
  111.     if (!Latt.empty() || !Ratt.empty())
  112.       return false;
  113.  
  114. /*|Latt| and |Ratt| are empty; we record the placement of the subsegments
  115.  * in |alpha|. */
  116.  
  117.     edge e;
  118.      forall(e, Lseg) alpha[e] = left;
  119.  
  120.      forall(e, Rseg) alpha[e] = right;
  121.  
  122.      return true;
  123.   }
  124.   void add_to_Att(list < int >&Att, int dfsnum_w0, edge_array < int >&alpha) {
  125. /* add the block to the rear of |Att|. Flip if necessary */
  126.     if (!Ratt.empty() && head_of_Ratt() > dfsnum_w0)
  127.       flip();
  128.  
  129.     Att.conc(Latt);
  130.     Att.conc(Ratt);
  131. /* This needs some explanation. Note that |Ratt| is either empty
  132.  * or $\{w0\}$. Also if |Ratt| is non-empty then all subsequent sets are contained
  133.  * in $\{w0\}$. So we indeed compute an ordered set of attachments. */
  134.  
  135.     edge e;
  136.      forall(e, Lseg) alpha[e] = left;
  137.  
  138.      forall(e, Rseg) alpha[e] = right;
  139.   }
  140. };
  141.  
  142. void make_biconnected_graph(graph & G)
  143. {
  144.   node v;
  145.   node_array < bool > reached(G, false);
  146.   node u = G.first_node();
  147.  
  148.   forall_nodes(v, G) {
  149.     if (!reached[v]) {        /* explore the connected component with root
  150.                  * * |v| */
  151.       DFS(G, v, reached);
  152.       if (u != v) {        /* link |v|'s component to the first *
  153.                  * component */
  154.     G.new_edge(u, v);
  155.     G.new_edge(v, u);
  156.       }                /* end if */
  157.     }                /* end not reached */
  158.   }                /* end forall */
  159.  
  160. /* |G| is now connected. We next make it biconnected. */
  161.  
  162.   forall_nodes(v, G) reached[v] = false;
  163.   node_array < int >dfsnum(G);
  164.   node_array < node > parent(G, nil);
  165.   int dfs_count = 0;
  166.   node_array < int >lowpt(G);
  167.  
  168.   dfs_in_make_biconnected_graph(G, G.first_node(), dfs_count, reached, dfsnum, lowpt, parent);
  169.  
  170. }                /* end |make_biconnected_graph| */
  171.  
  172. static void dfs_in_make_biconnected_graph(graph & G, node v, int &dfs_count,
  173.   node_array < bool > &reached,
  174.   node_array < int >&dfsnum, node_array < int >&lowpt,
  175.   node_array < node > &parent)
  176. {
  177.  
  178.   node w;
  179.   edge e;
  180.  
  181.   dfsnum[v] = dfs_count++;
  182.   lowpt[v] = dfsnum[v];
  183.   reached[v] = true;
  184.  
  185.   if (!G.first_adj_edge(v))
  186.     return;            /* no children */
  187.  
  188.   node u = target(G.first_adj_edge(v));        /* first child */
  189.  
  190.   forall_adj_edges(e, v) {
  191.     w = target(e);
  192.     if (!reached[w]) {        /* e is a tree edge */
  193.       parent[w] = v;
  194.       dfs_in_make_biconnected_graph(G, w, dfs_count, reached, dfsnum, lowpt, parent);
  195.       if (lowpt[w] == dfsnum[v]) {    /* |v| is an articulation point. We * 
  196.                      * now add an edge. If |w| is the *
  197.                      * first child and |v| has a parent * 
  198.                      * then we connect |w| and *
  199.                      * |parent[v]|, if |w| is a first *
  200.                      * child and |v| has no parent then * 
  201.                      * we do nothing. If |w| is not the * 
  202.                      * first child then we connect |w| to 
  203.                      * 
  204.                      * * the first child. The net effect
  205.                      * of  * all of this is to link all * 
  206.                      * children of an articulation point
  207.                      * * to the first child and the first
  208.                      * * child to the parent (if it
  209.                      * exists)  */
  210.     if (w == u && parent[v]) {
  211.       G.new_edge(w, parent[v]);
  212.       G.new_edge(parent[v], w);
  213.     }
  214.     if (w != u) {
  215.       G.new_edge(u, w);
  216.       G.new_edge(w, u);
  217.     }
  218.       }                /* end if lowpt = dfsnum */
  219.       lowpt[v] = Min(lowpt[v], lowpt[w]);
  220.     }                /* end tree edge */
  221.     else
  222.       lowpt[v] = Min(lowpt[v], dfsnum[w]);    /* non tree edge */
  223.   }                /* end forall */
  224. }                /* end dfs */
  225.  
  226. static void reorder(graph & G, node_array < int >&dfsnum,
  227.   node_array < node > &parent)
  228. {
  229.   node v;
  230.   node_array < bool > reached(G, false);
  231.   int dfs_count = 0;
  232.   list < edge > Del;
  233.   node_array < int >lowpt1(G), lowpt2(G);
  234.  
  235.   dfs_in_reorder(Del, G.first_node(), dfs_count, reached, dfsnum, lowpt1, lowpt2, parent);
  236.  
  237. /* remove forward and reversals of tree edges */
  238.  
  239.   edge e;
  240.   forall(e, Del) G.del_edge(e);
  241.  
  242. /* we now reorder adjacency lists as described in \cite[page 101]{Me:book} */
  243.  
  244.   node w;
  245.   edge_array < int >cost(G);
  246.   forall_edges(e, G) {
  247.     v = source(e);
  248.     w = target(e);
  249.     cost[e] = ((dfsnum[w] < dfsnum[v]) ?
  250.       2 * dfsnum[w] :
  251.       ((lowpt2[w] >= dfsnum[v]) ?
  252.     2 * lowpt1[w] : 2 * lowpt1[w] + 1));
  253.   }
  254.  
  255.   G.sort_edges(cost);
  256.  
  257. }
  258.  
  259. static void dfs_in_reorder(list < edge > &Del, node v, int &dfs_count,
  260.   node_array < bool > &reached,
  261.   node_array < int >&dfsnum,
  262.   node_array < int >&lowpt1, node_array < int >&lowpt2,
  263.   node_array < node > &parent)
  264. {
  265.   node w;
  266.   edge e;
  267.  
  268.   dfsnum[v] = dfs_count++;
  269.   lowpt1[v] = lowpt2[v] = dfsnum[v];
  270.   reached[v] = true;
  271.   forall_adj_edges(e, v) {
  272.     w = target(e);
  273.     if (!reached[w]) {        /* e is a tree edge */
  274.       parent[w] = v;
  275.       dfs_in_reorder(Del, w, dfs_count, reached, dfsnum, lowpt1, lowpt2,
  276.     parent);
  277.       lowpt1[v] = Min(lowpt1[v], lowpt1[w]);
  278.     }                /* end tree edge */
  279.     else {
  280.       lowpt1[v] = Min(lowpt1[v], dfsnum[w]);    /* no effect for forward *
  281.                          * edges */
  282.       if ((dfsnum[w] >= dfsnum[v]) || w == parent[v])
  283. /* forward edge or reversal of tree edge */
  284.     Del.append(e);
  285.     }                /* end non-tree edge */
  286.  
  287.   }                /* end forall */
  288.  
  289. /* we know |lowpt1[v]| at this point and now make a second pass over all
  290.  * adjacent edges of |v| to compute |lowpt2| */
  291.  
  292.   {
  293.     forall_adj_edges(e, v) {
  294.       w = target(e);
  295.       if (parent[w] == v) {    /* tree edge */
  296.     if (lowpt1[w] != lowpt1[v])
  297.       lowpt2[v] = Min(lowpt2[v], lowpt1[w]);
  298.     lowpt2[v] = Min(lowpt2[v], lowpt2[w]);
  299.       }                /* end tree edge */
  300.       else
  301.       /* all other edges */ if (lowpt1[v] != dfsnum[w])
  302.     lowpt2[v] = Min(lowpt2[v], dfsnum[w]);
  303.     }                /* end forall */
  304.   }
  305. }                /* end dfs */
  306.  
  307. static bool strongly_planar(edge e0, graph & G, list < int >&Att,
  308.   edge_array < int >&alpha,
  309.   node_array < int >&dfsnum,
  310.   node_array < node > &parent)
  311. {
  312.  
  313.   node x = source(e0);
  314.  
  315.   node y = target(e0);
  316.  
  317.   edge e = G.first_adj_edge(y);
  318.  
  319.   node wk = y;
  320.  
  321.   while (dfsnum[target(e)] > dfsnum[wk]) {    /* e is a tree edge */
  322.     wk = target(e);
  323.     e = G.first_adj_edge(wk);
  324.   }
  325.  
  326.   node w0 = target(e);
  327.  
  328.   node w = wk;
  329.  
  330.   stack < block * >S;
  331.  
  332.   while (w != x) {
  333.     int count = 0;
  334.     forall_adj_edges(e, w) {
  335.       count++;
  336.       if (count != 1) {        /* no action for first edge */
  337.     list < int >A;
  338.  
  339.     if (dfsnum[w] < dfsnum[target(e)]) {    /* tree edge */
  340.       if (!strongly_planar(e, G, A, alpha, dfsnum, parent)) {
  341.         while (!S.empty())
  342.           delete(S.pop());
  343.         return false;
  344.       }
  345.  
  346.     }
  347.     else
  348.       A.append(dfsnum[target(e)]);    /* a back edge */
  349.  
  350.     block *B = new block(e, A);
  351.  
  352.     while (true) {
  353.       if (B->left_interlace(S))
  354.         (S.top())->flip();
  355.  
  356.       if (B->left_interlace(S)) {
  357.         delete(B);
  358.         while (!S.empty())
  359.           delete(S.pop());
  360.         return false;
  361.       };
  362.  
  363.       if (B->right_interlace(S))
  364.         B->combine(S.pop());
  365.       else
  366.         break;
  367.     }            /* end while */
  368.  
  369.     S.push(B);
  370.  
  371.       }                /* end if */
  372.     }                /* end forall */
  373.  
  374.     while (!S.empty() && (S.top())->clean(dfsnum[parent[w]], alpha))
  375.       delete(S.pop());
  376.  
  377.     w = parent[w];
  378.   }                /* end while */
  379.  
  380.   Att.clear();
  381.   while (!S.empty()) {
  382.     block *B = S.pop();
  383.  
  384.     if (!(B->empty_Latt()) && !(B->empty_Ratt()) &&
  385.       (B->head_of_Latt() > dfsnum[w0]) && (B->head_of_Ratt() > dfsnum[w0])) {
  386.       delete(B);
  387.       while (!S.empty())
  388.     delete(S.pop());
  389.       return false;
  390.     }
  391.  
  392.     B->add_to_Att(Att, dfsnum[w0], alpha);
  393.  
  394.     delete(B);
  395.   }                /* end while */
  396.  
  397. /* Let's not forget (as the book does) that $w0$ is an attachment of $S(e0)$
  398.  * except if $w0 = x$. */
  399.  
  400.   if (w0 != x)
  401.     Att.append(dfsnum[w0]);
  402.  
  403.   return true;
  404. }
  405.  
  406. static void embedding(edge e0, int t, GRAPH < node, edge > &G,
  407.   edge_array < int >&alpha,
  408.   node_array < int >&dfsnum,
  409.   list < edge > &T, list < edge > &A, int &cur_nr,
  410.   edge_array < int >&sort_num, node_array < edge > &tree_edge_into,
  411.   node_array < node > &parent, edge_array < edge > &reversal)
  412. {
  413.  
  414.   node x = source(e0);
  415.  
  416.   node y = target(e0);
  417.  
  418.   tree_edge_into[y] = e0;
  419.  
  420.   edge e = G.first_adj_edge(y);
  421.  
  422.   node wk = y;
  423.  
  424.   while (dfsnum[target(e)] > dfsnum[wk]) {    /* e is a tree edge */
  425.     wk = target(e);
  426.     tree_edge_into[wk] = e;
  427.     e = G.first_adj_edge(wk);
  428.   }
  429.  
  430.   node w0 = target(e);
  431.   edge back_edge_into_w0 = e;
  432.  
  433.   node w = wk;
  434.  
  435.   list < edge > Al, Ar;
  436.   list < edge > Tprime, Aprime;
  437.  
  438.   T.clear();
  439.   T.append(G[e]);        /* |e = (wk,w0)| at this point, line (2) */
  440.  
  441.   while (w != x) {
  442.     int count = 0;
  443.     forall_adj_edges(e, w) {
  444.       count++;
  445.       if (count != 1) {        /* no action for first edge */
  446.  
  447.     if (dfsnum[w] < dfsnum[target(e)]) {    /* tree edge */
  448.       int tprime = ((t == alpha[e]) ? left : right);
  449.       embedding(e, tprime, G, alpha, dfsnum, Tprime, Aprime, cur_nr, sort_num, tree_edge_into, parent, reversal);
  450.  
  451.     }
  452.     else {            /* back edge */
  453.       Tprime.append(G[e]);    /* $e$ */
  454.       Aprime.append(reversal[G[e]]);    /* reversal of $e$ */
  455.     }
  456.  
  457.     if (t == alpha[e]) {
  458.       Tprime.conc(T);
  459.       T.conc(Tprime);    /* $T = Tprime\ conc\ T$ */
  460.  
  461.       Al.conc(Aprime);    /* $Al = Al\ conc\ Aprime$ */
  462.  
  463.     }
  464.     else {
  465.       T.conc(Tprime);    /* $ T\ = T\ conc\ Tprime $ */
  466.  
  467.       Aprime.conc(Ar);
  468.       Ar.conc(Aprime);    /* $ Ar\ = Aprime\ conc\ Ar$ */
  469.  
  470.     }
  471.  
  472.       }                /* end if */
  473.     }                /* end forall */
  474.  
  475.     T.append(reversal[G[tree_edge_into[w]]]);    /* $(w_{j-1},w_j)$ */
  476.  
  477.     forall(e, T) sort_num[e] = cur_nr++;
  478.  
  479. /* |w|'s adjacency list is now computed; we clear |T| and prepare for the
  480.  * next iteration by moving all darts incident to |parent[w]| from |Al| and
  481.  * |Ar| to |T|. These darts are at the rear end of |Al| and at the front end
  482.  * of |Ar| */
  483.  
  484.     T.clear();
  485.  
  486.     while (!Al.empty() && source(Al.tail()) == G[parent[w]])
  487. /* |parent[w]| is in |G|, |Al.tail| in |H| */
  488.     {
  489.       T.push(Al.Pop());        /* Pop removes from the rear */
  490.     }
  491.  
  492.     T.append(G[tree_edge_into[w]]);    /* push would be equivalent */
  493.  
  494.     while (!Ar.empty() && source(Ar.head()) == G[parent[w]]) {    /* */
  495.       T.append(Ar.pop());    /* pop removes from the front */
  496.     }
  497.  
  498.     w = parent[w];
  499.   }                /* end while */
  500.  
  501.   A.clear();
  502.  
  503.   A.conc(Ar);
  504.   A.append(reversal[G[back_edge_into_w0]]);
  505.   A.conc(Al);
  506.  
  507. }
  508.  
  509. bool PLANAR(graph & Gin, bool embed)
  510. /* |Gin| is a directed graph. |planar| decides whether |Gin| is planar.
  511.  * If it is and |embed == true| then it also computes a
  512.  * combinatorial embedding of |Gin| by suitably reordering
  513.  * its adjacency lists.
  514.  * |Gin| must be bidirected in that case. */
  515.  
  516. {
  517.   int n = Gin.number_of_nodes();
  518.  
  519.   if (n <= 3)
  520.     return true;
  521.  
  522.   if (Gin.number_of_edges() > 6 * n - 12)
  523.     return false;
  524.  
  525. /* An undirected planar graph has at most $3n-6$ edges; a directed graph may
  526.  * have twice as many */
  527.  
  528.   GRAPH < node, edge > G;
  529.  
  530.   edge_array < edge > companion_in_G(Gin);
  531.  
  532.   node_array < node > link(Gin);
  533.  
  534.   bool Gin_is_bidirected = true;
  535.  
  536.   {
  537.     node v;
  538.     forall_nodes(v, Gin) link[v] = G.new_node(v);    /* bidirectional *
  539.                              * links */
  540.     edge e;
  541.     forall_edges(e, Gin) companion_in_G[e] =
  542.       G.new_edge(link[source(e)], link[target(e)], e);
  543.  
  544.   }
  545.  
  546.   {
  547.     node_array < int >nr(G);
  548.     edge_array < int >cost(G);
  549.     int cur_nr = 0;
  550.     int n = G.number_of_nodes();
  551.     node v;
  552.     edge e;
  553.  
  554.     forall_nodes(v, G) nr[v] = cur_nr++;
  555.  
  556.     forall_edges(e, G) cost[e] = ((nr[source(e)] < nr[target(e)]) ?
  557.       n * nr[source(e)] + nr[target(e)] :
  558.       n * nr[target(e)] + nr[source(e)]);
  559.  
  560.     G.sort_edges(cost);
  561.  
  562.     list < edge > L = G.all_edges();
  563.  
  564.     while (!L.empty()) {
  565.       e = L.pop();
  566. /* check whether the first edge on |L| is equal to the reversal of |e|. If so,
  567.  * delete it from |L|, if not, add the reversal to |G| */
  568.       if (!L.empty() && (source(e) == target(L.head())) && (source(L.head()) == target(e)))
  569.     L.pop();
  570.       else {
  571.     G.new_edge(target(e), source(e));
  572.     Gin_is_bidirected = false;
  573.       }
  574.     }
  575.  
  576.   }
  577.  
  578.   make_biconnected_graph(G);
  579.  
  580.   GRAPH < node, edge > H;
  581.   edge_array < edge > companion_in_H(Gin);
  582.  
  583.   {
  584.     node v;
  585.     forall_nodes(v, G) G.assign(v, H.new_node(v));
  586.  
  587.     edge e;
  588.     forall_edges(e, G) G.assign(e, H.new_edge(G[source(e)], G[target(e)], e));
  589.  
  590.     edge ein;
  591.     forall_edges(ein, Gin) companion_in_H[ein] = G[companion_in_G[ein]];
  592.   }
  593.  
  594.   edge_array < edge > reversal(H);
  595.  
  596.   compute_correspondence(H, reversal);
  597.  
  598.   node_array < int >dfsnum(G);
  599.   node_array < node > parent(G, nil);
  600.  
  601.   reorder(G, dfsnum, parent);
  602.  
  603.   edge_array < int >alpha(G, 0);
  604.  
  605.   {
  606.     list < int >Att;
  607.  
  608.     alpha[G.first_adj_edge(G.first_node())] = left;
  609.  
  610.     if (!strongly_planar(G.first_adj_edge(G.first_node()), G, Att, alpha, dfsnum, parent))
  611.       return false;
  612.   }
  613.  
  614.   if (embed) {
  615.     if (Gin_is_bidirected) {
  616.       list < edge > T, A;    /* lists of edges of |H| */
  617.  
  618.       int cur_nr = 0;
  619.       edge_array < int >sort_num(H);
  620.       node_array < edge > tree_edge_into(G);
  621.  
  622.       embedding(G.first_adj_edge(G.first_node()), left, G, alpha, dfsnum, T, A,
  623.     cur_nr, sort_num, tree_edge_into, parent, reversal);
  624.  
  625. /* |T| contains all edges incident to the first node except the cycle edge into it.
  626.  * That edge comprises |A| */
  627.  
  628.       T.conc(A);
  629.       edge e;
  630.  
  631.       forall(e, T) sort_num[e] = cur_nr++;
  632.  
  633.       edge_array < int >sort_Gin(Gin);
  634.  
  635.       {
  636.     edge ein;
  637.     forall_edges(ein, Gin) sort_Gin[ein] = sort_num[companion_in_H[ein]];
  638.       }
  639.  
  640.       Gin.sort_edges(sort_Gin);
  641.     }
  642.  
  643.     else
  644.       error_handler(2, "sorry: can only embed bidirected graphs");
  645.   }
  646.   return true;
  647. }
  648.  
  649. bool PLANAR(graph & G, list < edge > &P, bool embed)
  650. {
  651.   if (PLANAR(G, embed))
  652.     return true;
  653.  
  654. /* We work on a copy |H| of |G| since the procedure alters |G|; we link every
  655.  * vertex and edge of |H| with its original. For the vertices we also have the
  656.  * reverse links. */
  657.  
  658.   GRAPH < node, edge > H;
  659.   node_array < node > link(G);
  660.   node v;
  661.   forall_nodes(v, G) link[v] = H.new_node(v);
  662. /* This requires some explanation. |H.new_node(v)| adds a new node to
  663.  * |H|, returns the new node, and makes |v| the information associated
  664.  * with the new node. So the statement creates a copy of |v| and
  665.  * bidirectionally links it with |v| */
  666.  
  667.   edge e;
  668.   forall_edges(e, G) H.new_edge(link[source(e)], link[target(e)], e);
  669. /* |link[source(e)]| and |link[target(e)]| are the copies of |source(e)|
  670.  * and |target(e)| in |H|. The operation |H.new_edge| creates a new edge
  671.  * with these endpoints, returns it, and makes |e| the information of that
  672.  * edge. So the effect of the loop is to make the edge set of |H| a copy
  673.  * of the edge set of |G| and to let every edge of |H| know its original.
  674.  * We can now determine a minimal non-planar subgraph of |H| */
  675.   list < edge > L = H.all_edges();
  676.  
  677.   edge eh;
  678.  
  679.   forall(eh, L) {
  680.     e = H[eh];            /* the edge in |G| corresponding to |eh| */
  681.     node x = source(eh);
  682.     node y = target(eh);
  683.     H.del_edge(eh);
  684.     if (PLANAR(H))
  685.       H.new_edge(x, y, e);    /* put a new version of |eh| back in and *
  686.                  * establish the correspondence */
  687.  
  688.   }
  689.  
  690. /* |H| is now a homeomorph of either $K_5$ or $K_{3,3}$. We still need
  691.  * to translate back to |G|. */
  692.  
  693.   P.clear();
  694.  
  695.   forall_edges(eh, H) P.append(H[eh]);
  696.  
  697.   return false;
  698.  
  699. }
  700.